package leetcode.code0526;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {

	int n;

	public int countArrangement(int n) {
		this.n = n + 1;
		int[] dp = new int[1 << n];
		Arrays.fill(dp, -1);
		return this.countArrangement(1, (1 << n) - 1, dp);
	}

	private int countArrangement(int index, int nums, int[] dp) {
		if (index == n) {
			return 1;
		}
		if (dp[nums] != -1) {
			return dp[nums];
		}
		int num = 1;
		int cur = nums, used = 1;
		int ans = 0;
		while (cur > 0) {
			if ((cur & 1) == 1 && (num % index == 0 || index % num == 0)) {
				ans += this.countArrangement(index + 1, nums ^ used, dp);
			}
			cur >>= 1;
			num += 1;
			used <<= 1;
		}
		dp[nums] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
